package recursive.generateTrees;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;
/**
 * @Date 2020/04/07
 * @author 王光浩
 * @Thinking 使用备忘录+递归
 */
public class MyMethodTwo {
		public List<TreeNode> generateTrees(int n) {
			if(n==0)return new LinkedList<TreeNode>();
			HashMap<String,List<TreeNode>> map=new HashMap<String,List<TreeNode>>();
			return helper(1,n,map);
	    }
		/**
		 * 将所有 在left~right范围内，分别以left到right为root的所有二叉搜索树加入到List<TreeNode>
		 * @param n
		 * @param level
		 */
		private List<TreeNode> helper(int left,int right,HashMap<String,List<TreeNode>> map) {
			List<TreeNode> ret=new LinkedList<TreeNode>();
			String key=left+","+right;
			if(left>right) {
				ret.add(null);
				map.put(key, ret);
			}
			else if(map.containsKey(key))return map.get(key);
			else if(left==right) {
				ret.add(new TreeNode(left));
				map.put(key, ret);
			}
			else {
				for(int i=left;i<=right;i++) {
					List<TreeNode> leftList=helper(left,i-1,map);
					List<TreeNode> rightList=helper(i+1,right,map);
					for(TreeNode temLeft:leftList) {
						for(TreeNode temRight:rightList) {
							TreeNode root=new TreeNode(i);
							root.left=temLeft;
							root.right=temRight;
							ret.add(root);
						}
					}
				}
				map.put(key, ret);
			}
			return map.get(key);
		}
}

